{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## **实验七 稀疏矩阵的存储和快速转置**\n",
    "要求：输入一个稀疏矩阵A，由程序将其转换成三元组表存储；转置后的三元组表，由程序将其转换成矩阵形式后输出。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "稀疏矩阵A为:\n",
      "   0   1   2  3  4  5\n",
      "0  2   5   0  0  0  0\n",
      "1  0  11   3  0  0  0\n",
      "2  0   0   0 -6  0  0\n",
      "3  0   0   0  0  0  0\n",
      "4  0   9   0  0  0  1\n",
      "5  0   0  21  0  0  0\n",
      "零初始化矩阵newA为:\n",
      "   0  1  2  3  4  5\n",
      "0  0  0  0  0  0  0\n",
      "1  0  0  0  0  0  0\n",
      "2  0  0  0  0  0  0\n",
      "3  0  0  0  0  0  0\n",
      "4  0  0  0  0  0  0\n",
      "5  0  0  0  0  0  0\n"
     ]
    }
   ],
   "source": [
    "from pandas import DataFrame as df\n",
    "\n",
    "# 设一个稀疏矩阵为A\n",
    "A = [[2, 5, 0, 0, 0, 0], [0, 11, 3, 0, 0, 0],\n",
    "     [0, 0, 0, -6, 0, 0], [0, 0, 0, 0, 0, 0],\n",
    "     [0, 9, 0, 0, 0, 1], [0, 0, 21, 0, 0, 0]]\n",
    "\n",
    "rows = len(A)  \n",
    "cols = len(A[0])\n",
    "newA = [[0] * cols for row in range(rows)] #声明新的稀疏矩阵，以全零初始化\n",
    "print('稀疏矩阵A为:')\n",
    "print(DataFrame(A))\n",
    "print('零初始化矩阵newA为:')\n",
    "print(DataFrame(newA))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# 稀疏矩阵压缩存储函数\n",
    "def CompressArray(A):  \n",
    "    global Compress\n",
    "    NonZero = 0\n",
    "    temp = 1\n",
    "    print(\"原稀疏矩阵为：\")\n",
    "    for i in range(rows):\n",
    "        for j in range(cols):\n",
    "            print('%d' % A[i][j], end='\\t')\n",
    "            if A[i][j] != 0:\n",
    "                NonZero += 1\n",
    "        print()\n",
    "\n",
    "    # 声明压缩矩阵\n",
    "    Compress = [[None] * 3 for row in range(NonZero + 1)]\n",
    "\n",
    "    # 构造稀疏矩阵压缩存储\n",
    "    Compress[0][0] = rows\n",
    "    Compress[0][1] = cols\n",
    "    Compress[0][2] = NonZero\n",
    "\n",
    "    for i in range(rows):\n",
    "        for j in range(cols):\n",
    "            if A[i][j] != 0:\n",
    "                Compress[temp][0] = i\n",
    "                Compress[temp][1] = j\n",
    "                Compress[temp][2] = A[i][j]\n",
    "                temp += 1\n",
    "#     print(DataFrame(Compress))\n",
    "    return Compress\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 输出压缩矩阵函数\n",
    "def OutputComArray(Compress):  \n",
    "    print('稀疏矩阵压缩存储内容为：')\n",
    "    for i in range(len(Compress)):\n",
    "        for j in range(3):\n",
    "            print('%d' % Compress[i][j], end=' ')\n",
    "        print()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "def TriplesToSparse(Compress, Sprase):  #以三元组的行列为索引号替换新稀疏矩阵的0\n",
    "    for i in range(1,len(Compress)):\n",
    "        row = int(Compress[i][0])\n",
    "        col = int(Compress[i][1])\n",
    "        Sprase[row][col] = int(Compress[i][2])\n",
    "    print('三元组转换成新的稀疏矩阵并输出：')\n",
    "    for i in range(rows):\n",
    "        for j in range(cols):\n",
    "            print('%d'%Sprase[i][j],end = '\\t')\n",
    "        print()\n",
    "    return DataFrame(Sprase)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原稀疏矩阵为：\n",
      "2\t5\t0\t0\t0\t0\t\n",
      "0\t11\t3\t0\t0\t0\t\n",
      "0\t0\t0\t-6\t0\t0\t\n",
      "0\t0\t0\t0\t0\t0\t\n",
      "0\t9\t0\t0\t0\t1\t\n",
      "0\t0\t21\t0\t0\t0\t\n",
      "稀疏矩阵压缩存储内容为：\n",
      "6 6 8 \n",
      "0 0 2 \n",
      "0 1 5 \n",
      "1 1 11 \n",
      "1 2 3 \n",
      "2 3 -6 \n",
      "4 1 9 \n",
      "4 5 1 \n",
      "5 2 21 \n"
     ]
    }
   ],
   "source": [
    "CompressArray(A)\n",
    "OutputComArray(Compress)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "三元组转换成新的稀疏矩阵并输出：\n",
      "2\t5\t0\t0\t0\t0\t\n",
      "0\t11\t3\t0\t0\t0\t\n",
      "0\t0\t0\t-6\t0\t0\t\n",
      "0\t0\t0\t0\t0\t0\t\n",
      "0\t9\t0\t0\t0\t1\t\n",
      "0\t0\t21\t0\t0\t0\t\n",
      "   0   1   2  3  4  5\n",
      "0  2   5   0  0  0  0\n",
      "1  0  11   3  0  0  0\n",
      "2  0   0   0 -6  0  0\n",
      "3  0   0   0  0  0  0\n",
      "4  0   9   0  0  0  1\n",
      "5  0   0  21  0  0  0\n"
     ]
    }
   ],
   "source": [
    "print(TriplesToSparse(Compress, newA))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
